package search;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class IntervalContainer {

	/*
	 * This method will terminate when it finds an interval that can be contained.
	 * Which pair will be returned is not guaranteed, however, this method is guaranteed
	 * to return at least one pair if such pairs exist.
	 * 
	 * Limitation: This methods is running linearly after sorting intervals so it can't 
	 * return all such pairs. 
	 * 
	 * */
	public static Interval findIntervalContainer(List<Interval> listInterval){
		Collections.sort(listInterval); // O(n * log n)
		System.out.println("Sorted intervals: "+listInterval);
		
		// linear scan to find the pair that can be contained
		int size = listInterval.size();
		for(int index = 0; index < size; index++){ // O(n)
			if(index+1 < size && listInterval.get(index).high >= listInterval.get(index+1).high){
				return listInterval.get(index+1);
			}
		}
	
		return null; // no such pair found
	}


	public static int[] displayTopViewOfOverlappedLineSegments(List<Interval> lineSegments){
		
		// assumption is smallest low >= 0 and largest high <= 40.
		// otherwise calculate smallest low and largest high of all the segments
		int[] line = new int[40]; // line of 40 pixels
		int index = 0;
		while(index < 40){ // create the blank line, -1 denotes no color
			line[index++] = -1;
		}
		
		// sort the line segments by height
		Collections.sort(lineSegments, new HeightComparator()); // O(n * log n)
		System.out.println("Sorted intervals based on Height: "+lineSegments);
		
		// segment must come in order of the heights
		for(Interval segment : lineSegments){
			for(int i = segment.low - 1; i < segment.high; i++){
				line[i] = segment.height; // for simplicity height is same as color code
			}
		}
		
		// return line (set of pixels)
		return line;
	}
}


// Interval class
class Interval implements Comparable<Interval>{
	int low, high, height;
	
	Interval(int low, int high, int height){
		this.low = low;
		this.high = high;
		this.height = height; // added due to method displayTopViewOfOverlappedLineSegments
	}

	public String toString(){
		return "{"+low+","+high+","+height+"}";
	}

	public int compareTo(Interval anotherInterval) {
		// null check for anotherInterval not implemented
		// throw runtime exception in case anotherInterval is null
		
		int lowDifference = low - (anotherInterval).low;
		int highDifference = 0;
		
		if(lowDifference == 0){
			highDifference = high - (anotherInterval).high;
		}else{
			return lowDifference;
		}
		return highDifference;
	}
}


// height comparator: sorts the line segments based on height
class HeightComparator implements Comparator<Interval>{

	public int compare(Interval interval1, Interval interval2) {
		return interval1.height - interval2.height;
	}
	
}
